/**
 * @author: mattwang@tencent.com
 * @date: 2012-9-25
 */

#ifndef __TYPE_DEF_H__
#define __TYPE_DEF_H__

#include <assert.h>
#include <vector>
#include <ext/hash_set>
#include <ext/hash_map>
#include "mpi_def.h"

#define info(fmt, ...) printf("[%d/%d]-[%s():%d]"fmt"\n", g_mpi_rank, g_mpi_size,__func__, __LINE__, ##__VA_ARGS__)

using std::vector;

typedef std::vector<double> DVector;

const double eps = 1e-12;
static inline int dcmp(double x) {
	return x < -eps ? -1 : x > eps;
}

template<typename DATA, typename VALUE>
void sort_by_value(DATA *data, VALUE *power, uint32_t begin, uint32_t end) {
	if (begin >= end)
		return;

	if (begin + 1 == end) {
		if (power[begin] < power[end]) {
			VALUE value = power[begin];
			power[begin] = power[end];
			power[end] = value;

			DATA d = data[begin];
			data[begin] = data[end];
			data[end] = d;
		}
		return;
	}

	uint32_t mid = (begin + end) >> 1;
	float mid_value = power[mid];
	uint32_t m = begin;
	uint32_t n = end;

	while (begin < end) {
		while (begin < end && mid_value < power[begin]) {
			begin++;
		}
		while (begin < end && mid_value > power[end]) {
			end--;
		}

		if (begin < end) {
			VALUE value = power[begin];
			power[begin] = power[end];
			power[end] = value;

			DATA d = data[begin];
			data[begin] = data[end];
			data[end] = d;

			if (++begin < end)
				end--;
		}
	}

	if (mid_value < power[begin])
		begin++;

	if (m < begin)
		sort_by_value<DATA, VALUE>(data, power, m, begin - 1);
	if (n > end)
		sort_by_value<DATA, VALUE>(data, power, end, n);
}

const static unsigned char bitmap_mark[] = { 1, 2, 4, 8, 16, 32, 64, 128 };

typedef struct __bitmap {
	unsigned char *map_buff;
	int real_size;

	void reset() {
		memset(map_buff, 0, real_size);
	}
	inline void set(int n) {
		int pos = n / 8;
		int i = n % 8;
		map_buff[pos] |= bitmap_mark[i];
	}
	inline void unset(int n) {
		int pos = n / 8;
		int i = n % 8;
//		unsigned char old = map_buff[pos];
		map_buff[pos] &= ~bitmap_mark[i];
//		log("%x=%x  %x %d", old, map_buff[pos], ~bitmap_mark[i], i);
	}
	inline int get(int n) {
		int pos = n / 8;
		int i = n % 8;
		unsigned char v = map_buff[pos] & bitmap_mark[i];
//		log("%x=%x  %x %d", v, map_buff[pos], bitmap_mark[pos], i);
		return (v == 0) ? 0 : 1;
	}
	unsigned char *buff() {
		return map_buff;
	}
	__bitmap() {
		map_buff = NULL;
	}

	inline void resize(int size)
	{
		if(map_buff) delete[] map_buff;
		real_size = size / 8 + ((size % 8) != 0);
		map_buff = new unsigned char[real_size];
		reset();
	}

	__bitmap(int size) {
		real_size = size / 8 + ((size % 8) != 0);
		map_buff = new unsigned char[real_size];
		reset();
	}
	~__bitmap() {
		delete[] map_buff;
	}
} Bitmap;

inline double RandDouble() {
	return rand() / static_cast<double>(RAND_MAX);
}

inline int RandInt(int bound) {
	// NOTE: Do NOT use rand() % bound, which does not approximate a
	// discrete uniform distribution will.
	return static_cast<int>(RandDouble() * bound);
}

#endif
